package day01;

/**
 * @author aiPlusPlus
 * @version 1.0
 * @date 2022/12/1 20:11
 */

import java.util.LinkedList;

/**
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 * 示例 2：
 *
 * 输入：height = [4,2,0,3,2,5]
 * 输出：9
 */
public class Solution3 {
    //方法一前后缀分解
    /*public int trap(int[] height) {
        int n = height.length;
        int []pre = new int[n];
        pre[0] = height[0];
        int []sre = new int[n];
        sre[n-1] = height[n-1];
        for (int i = 1; i < n; i++) {
            if(height[i]>pre[i-1]){
                pre[i] = height[i];
            }else {
                pre[i] = pre[i-1];
            }
        }
        for(int i = n-2;i>=0;i--){
            if(height[i]>sre[i+1]){
                sre[i] = height[i];
            }else {
                sre[i] = sre[i+1];
            }
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            count+=Math.min(sre[i],pre[i])-height[i];
        }
        return count;
    }*/
    //双指针
    /*public int trap(int[] height){
        int left = 0,right = height.length-1;
        int maxLeft = height[left],maxRight = height[right];
        int count = 0;
        while (left<right){
            if(maxLeft<maxRight){
                if(height[left+1]>maxLeft){
                    maxLeft = height[left+1];
                }else {
                    count+=(maxLeft-height[left+1]);
                }
                left++;
            }else {
                if(height[right-1]>maxRight){
                    maxRight = height[right-1];
                }else {
                    count+=(maxRight-height[right-1]);
                }
                right--;
            }
        }
        return count;
    }*/
    //单调栈
    public int trap(int[] height){
        LinkedList<Integer> stack = new LinkedList<>();
        int count = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty()&&height[i]>height[stack.peekLast()]){
                Integer integer = stack.pollLast();
                if(stack.isEmpty()){
                    break;
                }
                int len = i-stack.peekLast()-1;
                int wide = Math.min(height[stack.peekLast()],height[i])-height[integer];
                count+=(len*wide);
            }
            stack.add(i);
        }
        return count;
    }
}
